// https://www.lintcode.com/problem/climbing-stairs/description
// 描述
// 假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？
// 样例
// 比如n=3，1+1+1=1+2=2+1=3，共有3种不同的方法
// 返回 3
class Solution {
public:
    /**
     * @param n: An integer
     * @return: An integer
     */
    int climbStairs(int n) {
        if (n == 1 || n == 2){
            return n;
        }
        else{
            // return climbStairs(n - 1) + climbStairs(n - 2);
            int *step = new int[n];
            step[0] = 1;
            step[1] = 2;
            for (int i = 2; i < n; i++) {
                step[i] = step[i - 1] + step[i - 2];
            }
            return step[n - 1];
        }
    }
};